#include <cstdio>
#include <queue>
#include <vector>

using namespace std;

struct Node
{
    int v, cost;
    Node( ) { }
    Node( int _v, int _cost )
        : v( _v ), cost( _cost ) { }
};

vector<Node> li[ 101 ];
int n, m, d[ 101 ];

void init( )
{
    int i, j, a, b, c;
    for ( i = 1; i <= n; i++ )
        li[ i ].clear( );
    for ( i = 0; i < m; i++ )
    {
        scanf("%d%d%d", &a, &b, &c);
        li[ a ].push_back( Node( b, c ) );
        li[ b ].push_back( Node( a, c ) );
    }
}

bool relax( int u, int v, int cost )
{
    if ( d[ v ] > d[ u ] + cost )
    {
        d[ v ] = d[ u ] + cost;
        return true;
    }
    return false;
}

void spfa( )
{
    int i, j, p;
    for ( i = 1; i <= n; i++ )
        d[ i ] = 0xfffffff;
    queue<int> q;
    d[ n ] = 0;
    q.push( n );
    while ( !q.empty( ) )
    {
        p = q.front( );
        q.pop( );
        for ( i = 0; i < li[ p ].size( ); i++ )
            if ( relax( p, li[ p ][ i ].v, li[ p ][ i ].cost ) )
                q.push( li[ p ][ i ].v );
    }
    printf("%d\n", d[ 1 ]);
}

int main( )
{
    while ( scanf("%d%d", &n, &m) != EOF )
    {
        if ( n == 0 && m == 0 )
            break;
        init( );
        spfa( );
    }
    return 0;
}
